package oj;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 郝文雪
 * @date 2022/8/26 17:56
 * @Description Test
 */
public class LC417 {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> res=new ArrayList<>();
        int n=heights.length;
        int m=heights[0].length;
        boolean[][] reachP=new boolean[n][m];
        boolean[][] reachA=new boolean[n][m];
        for(int i=0;i<n;i++){
            dfs(heights,reachP,i,0);
            dfs(heights,reachA,i,m-1);
        }
        for(int i=0;i<m;i++){
            dfs(heights,reachP,0,i);
            dfs(heights,reachA,n-1,i);
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(reachA[i][j] && reachP[i][j]){
                    res.add(Arrays.asList(i,j));
                }
            }
        }
        return res;
    }
    private void dfs(int[][] heights,boolean[][] reach,int i,int j){
        if(reach[i][j]) return;
        reach[i][j]=true;
        if(i+1<heights.length && heights[i+1][j]>=heights[i][j]){
            dfs(heights,reach,i+1,j);
        }
        if(i-1>=0&&heights[i-1][j]>=heights[i][j]){
            dfs(heights,reach,i-1,j);
        }
        if(j+1<heights[0].length&&heights[i][j+1]>=heights[i][j]){
            dfs(heights,reach,i,j+1);
        }
        if(j-1>=0&&heights[i][j-1]>=heights[i][j]){
            dfs(heights,reach,i,j-1);
        }
    }
}
